package algorithm.leetcode.I1to100;

import java.util.*;

/**
 * 和第51题一样,不解释,直接看Q51就行
 * 这题没什么意思
 */

public class Q52 {

    public int totalNQueens(int n) {
        // 一些准备工作
        List<List<String>> result = new LinkedList<>();
        List<Integer> current = new LinkedList<>();
        boolean[] isUsed = new boolean[n];
        int[] availableNums = new int[n];
        for (int i = 0; i < availableNums.length; i++) {
            availableNums[i] = i;
        }
        // 调用核心方法
        backTrack(result, current,isUsed, availableNums, n);
        return result.size();
    }

    // 单独把这个打印函数抽离出来是为了保证单一职责,实际上可以在backTrack方法中添加满足要求的临时解实现
    private List<String> printQueen(List<Integer> solution, int n) {
        List<String> singleSolution = new LinkedList<>();
        for (Integer queenPosi : solution) {
            char[] temp = new char[n];
            Arrays.fill(temp, '.');
            temp[queenPosi] = 'Q';
            singleSolution.add(new String(temp));
        }
        return singleSolution;
    }

    private void backTrack(List<List<String>> result,
                           List<Integer> current,
                           boolean[] isUsed,
                           int[] availableNums,
                           int n) {

        // 检查当前解是否满足N皇后互不攻击,不满足,剪枝(即结束)
        if (!isLegal(current)) return;
        // if (isLegal(current) && current.size() == n) result.add(new LinkedList<>(current));
        if (isLegal(current) && current.size() == n) result.add(printQueen(current, n));

        // 向后枚举
        for (int i = 0; i < availableNums.length; i++) {
            if (!isUsed[i]) {
                isUsed[i] = true;
                current.add(availableNums[i]);
                backTrack(result, current, isUsed, availableNums, n);
                isUsed[i] = false;
                current.remove(current.size()-1);
            }
        }
    }

    // 这个判断有点精彩
    private boolean isLegal(List<Integer> current) {
        int size = current.size();
        // 不能在同一横行
        Set<Integer> rowConflict = new HashSet<>(current);
        // 左下至右上的对角线不能冲突,也就是i+current.get(i)不能有重复
        Set<Integer> ascDiagConflict = new HashSet<>();
        // 左上至右下的对角线不能冲突,也就是i-current.get(i)不能有重复
        Set<Integer> descDiagConflict = new HashSet<>();
        for (int i = 0; i < current.size(); i++) {
            ascDiagConflict.add(i + current.get(i));
            descDiagConflict.add(i - current.get(i));
        }
        return rowConflict.size() == size &&
                ascDiagConflict.size() == size &&
                descDiagConflict.size() == size;
    }

    public static void main(String[] args) {
        Q52 q52 = new Q52();
        int ans = q52.totalNQueens(4);
        System.out.println(ans);
    }
}
